908 348
872686974 71521281 158659155 756316196 114702334 772989169 807384455 550807307 480792741 404803038 96742532 133072903 260213960 814700018 377287889 818038468 773492032 379134844 568248250 665858132 125231851 404818029 389023438 249386410 634441002 215180507 72471647 108938270 456560226 598332289 601183749 777515500 524943483 277871677 786867483 968282804 997867364 255414930 621582144 232907772 571195789 38090788 757057752 98394537 395804267 332465470 329809289 107720842 59852023 697044815 752947902 682389709 906189359 941147496 907251239 942601352 339094932 27787968 8742967 649677873 838832555 804437808 279416485 184574246 338417788 259217848 750724844 806481447 594331670 755009272 570293962 6865879 410841353 21295544 355780805 94252862 361843946 605481312 100329633 357265481 612242642 518208640 785728491 762217033 446882784 398610250 955265650 997636720 85368242 262776851 241349832 993501271 86021872 742373846 658936005 373393531 675259330 664729776 208467972 955200187 498523732 250072677 611499109 288828124 227021657 969188058 864967817 723853061 609659013 182392473 339314265 461201475 480278802 235992400 325099392 265170182 84535356 144618578 497227756 911759266 424588229 578082068 131394129 744754384 312410226 319517617 893027494 65275434 589079691 437283687 945638053 263950514 20976735 85445912 426361935 779621196 958257854 206977482 465392742 176796479 403730813 953947943 693012210 105278135 91163638 462988798 312650685 709181766 61475717 853880000 90192599 617241183 427790860 568932867 661061906 852686298 327761007 856609539 404851846 620292723 342496025 250604572 990705423 773962827 13232758 709481809 310585034 236406117 62358903 738709705 840777372 247224362 286928913 457998668 457767595 757219302 262403518 986544842 878373090 13556040 898553338 733628116 699393906 375778022 255917767 3351841 879855947 640890295 143975210 155776523 737442471 6201751 746311595 646922511 512723840 958308806 766555865 457712465 731631125 344635753 371794884 485025813 672978793 413720072 259814529 507463495 240356292 109719566 534210218 495599604 800380208 181542221 716720603 256209615 174259709 259828599 920426550 443618477 389992253 99460774 341042400 922268425 596240713 596523989 367916162 775107713 656607290 840281444 505717704 984309591 790428784 163996568 672178661 410960368 96506639 108118296 185002254 238017368 601753213 316457841 717923578 911013309 125805286 596943252 800861545 929060592 78760120 361582163 343387290 658624743 688078631 528469735 392321490 746003006 623777450 544386413 76561884 95666865 735132540 642076516 178637700 265403811 367022620 49186864 492249115 869141146 931881933 951175578 677521398 831573440 129040663 410992719 181099247 887346788 535007300 662387292 533015778 862487415 306621924 844650936 619155505 670467088 319392585 630672571 331484225 143982056 821528844 210320543 964327931 55613407 415535494 712759302 230072908 452041845 844107608 118453107 363284645 677879377 812048355 809877967 758955899 14706878 842954193 161330406 733694152 752707113 27857802 221578728 738061448 324509860 251832768 843006952 773476157 895048294 115005924 580112992 182349932 916637769 146235054 666263979 337613086 458713675 845236377 238704522 495812192 226331661 832069732 318086048 47771587 22671703 875504530 488366070 732742620 36434066 224601835 750648696 466937541 285912396 482879225 550395509 374692507 493649080 14409356 92065059 91433982 640292395 61639478 989186584 675537044 691311520 925730768 942871250 939092869 954462773 798653171 964580401 752195072 630298796 587008896 470347511 69684149 151338475 121405209 530945615 298084698 801760124 928521381 784620611 463547175 632236558 363113680 417276485 929922393 234310130 385894536 133131175 580083890 791491999 753920897 453588514 974771447 46897710 774332082 119550035 818088817 538491870 659208918 115290169 843514733 488308881 361865452 233412537 103440060 529822798 463938232 128145690 30247476 355039677 349626176 793775498 278368300 434287278 631099727 932107159 10026244 668194450 49100277 249996726 797463963 204081920 92788996 572716735 156429271 33221682 90626453 480774766 711925537 761639813 179293314 926542820 403874534 54548477 202876137 64943141 647898391 292069566 107007663 268923544 995534506 772784020 941260026 286011786 27022870 937276780 363743926 181478571 155654107 250674905 509377810 867431823 395059960 173853328 828748800 830257198 207598963 245975532 886381240 796536164 483021013 681096042 828033589 960882 128308907 544520494 716791222 911164027 121854214 585350525 308781375 221594376 559689468 636477761 986113046 397194885 962951973 211784328 972809030 39915457 46808606 788424965 215413791 447996786 795568905 165364878 880955572 65322671 704187915 644963228 260232795 869138292 203770061 183064014 702505521 314993953 774544124 130212966 92388756 275877627 677235402 561257162 165820583 477547178 123995498 597280004 175217873 730662073 231319 628422211 329886014 492092186 673796622 612816216 843326300 836308383 637453839 732005178 478823264 842050178 780364768 855332738 70826687 632272606 659024714 529863920 408199349 328879923 974345754 624350180 497409217 64420838 839342753 940677861 683138855 35116990 354286645 642745630 518951788 96692329 885686190 109218012 591879902 720333557 296947689 769885201 488257290 559891543 901317705 508626132 537460804 171405287 70888241 245524447 746144290 289255906 321904779 107724560 566190593 949256679 579954756 536432616 115132799 142579579 280263885 469083151 328754431 544877189 5919132 440987086 325554216 597270482 96508329 163595411 191301734 448538002 72820209 623378289 509783400 723597273 945011703 777892253 164156832 959726367 15299646 547571442 616486598 761298624 854771920 377926254 75051606 474317181 147328954 656953011 300573709 896122362 754699661 12691591 277593199 908060990 42822623 92776276 947322692 615335222 788199880 829726120 959734295 336696113 238090854 628627894 956717238 16106085 649591129 16697300 597524405 287324777 396211527 111017211 157967083 921258937 676481113 805968203 271221746 520269878 854438076 278242436 703535787 343498147 662763810 892631693 267033528 916272169 613720894 601348592 479226113 530148051 676239948 354672220 191045680 471544339 221141382 22075682 628538676 923414075 239290544 567954873 470851778 770550789 641993869 158339643 797319375 996721932 641717607 336368613 995986711 737803857 161361803 674132379 184066458 581778103 265713610 731329633 830265113 25875846 794256378 139124195 785004957 401029868 204567923 192090350 823600881 216338039 767202195 948861941 275137827 276450204 163257402 742923661 369801479 645461556 67082831 768002289 538342068 152947961 74666041 922310782 996589061 817496078 119068262 40009272 224454424 418491764 669359047 257607748 346766035 51936150 4908626 781734252 245492570 77732286 502565247 856218014 822543514 875349149 117722828 688056429 862216386 363640007 735039033 56706446 221403332 986169140 763095245 114815325 503371481 457266625 203088143 41113430 398135034 507269037 58131853 193015964 481932647 717533724 324216665 152453237 716472100 397861528 2897030 681351371 260170871 399680907 427009200 114509997 418359660 689482437 72250737 205376204 652919889 463459836 409318637 575834622 391980090 591450951 264265799 244497855 438603134 161032611 126601769 153080491 439455288 667506030 428700481 442197253 558908103 186768111 698888382 872811316 644350030 849377484 238340823 504242240 75325749 60200081 461196100 492430425 248419238 500154160 927061443 282900305 381354512 23277948 141498004 958834973 160493480 515253421 329488638 433036887 25987299 819787999 730733000 757198015 105298942 812166034 547959232 768675765 15438198 243073579 556044344 814915777 535106192 374524530 848555395 388964876 5698514 692164371 725262717 745993444 311116680 870550557 111908865 402018876 105529408 425117573 619244400 579643177 296444238 836698020 686701360 775355238 908576073 679772085 815482411 879491025 326486668 455853656 676319052 420412140 891807670 255202322 294683142 346571101 757290538 117082059 737939660 906072174 477774480 376384846 951706 125814925 126994258 79737804 924685419 683621837 669815584 495616601 402421184 152079972 309047149 586474606 680246559 865863979 282323183 287983205 464631698 944951329 972462114 559417857 934205476 517509352 648083398 718855395 236658792 454976326 613320541 531316501 57652978 464032166 10694062 347940228 782603227 975295381 207502149 332792446 231437121 29864005 713656560 371825720 554155972 63878925 10068035 756700490 51407115 817664998 162171413 449041200 23060541 764831728 412689665 481132235 948599945 102227435 423356390 890025182 64457118 815158463 763872360 31617171 749794867 984508404 9763180 708533235 274806912 424319034 961824672 175520881 467371203 40252899 934576113 765908832 876287421 50870628 731366418 671405176 439037234 356181464 677378812 729807957 758007917 9052540 746933608 527735032 869863609 349285428 720112215 539461188 81496553 752345605 896912267 975995010
677887697 403796377 658492427 788146398 615731146 672887486 920381091 244816359 26840882 903635687 275251809 80719379 949879786 550592425 209813273 963250744 730450390 894712639 558145506 111625748 509789281 708115207 253064087 176475847 371991798 950626307 688461144 750818644 415808392 115468121 153594118 645949731 891152139 427938004 61301706 193035906 98946040 29494112 561817742 587862303 53738701 243490705 342291074 249372304 811480203 907661341 243518873 852132043 537949494 373767261 637035273 35164334 368120921 770697937 452530127 149812856 341331839 520651161 525198121 240958030 670821051 964146428 500817178 510760119 928833825 283936229 569725673 332193569 305755466 854601313 26408354 178393178 866745300 700771362 13914259 592004375 752892896 306774271 667747792 368043632 979362195 519500146 509446321 986381922 974530197 465987352 257173071 678129740 456227989 876430133 922839050 967680370 842491842 218021165 577733125 136554877 235728211 429680396 16115624 99577081 33559041 464334847 637534750 29802454 504463496 678275289 848186581 653839848 342111786 2181775 330214912 174425447 764087595 244360380 785254680 633256816 811828054 930730014 365818199 554850945 45064310 367621399 569603131 239412481 410901726 97594413 814006793 871212470 271575010 260859018 380001352 291499085 597509212 828701820 180920898 752073685 961141032 903906294 675638150 597658436 984479655 922582286 671998057 370420209 778699328 5563005 404609664 635919384 521582299 696753186 934745383 388614489 321234276 176264063 202559485 708906810 593024590 284547642 9975654 632308640 835585805 570219678 861505800 633532762 828782235 425576983 150728270 114736790 736942580 755321274 317526248 907180906 852623513 933734586 54153545 819800652 63919377 986085108 208645416 106970778 374965604 417668452 775716863 827712276 837143454 418007214 148279695 762830941 458422866 202295702 225333338 713139581 425616660 594638216 797485096 272328802 276200190 279077137 573535363 948474458 982675244 828330083 488485690 978988186 757644096 189054933 371767522 878799034 279097822 91892833 46787408 234214199 554077489 996871205 480815136 258479600 192509285 965560034 485057330 539568298 102182698 870793344 395440423 171148172 154136632 365305736 79618536 778420131 74340805 597526952 444846368 453781343 906342672 815325747 170115773 41040148 589151706 713423007 596591987 719009147 924445928 28383493 906653496 628888110 138299011 359433380 494828489 834803247 583879927 235371613 389515556 559548002 161018135 748404024 133529612 786702862 832015031 252847839 606256265 453031776 385899825 997727774 392783461 322222567 941971425 465055081 682955695 204368153 351261865 151174998 276617020 330601165 490966638 478988062 390755617 839324607 360626584 359563553 225913146 910163472 954631830 941172063 928544167 818360771 761147992 29910527 327434570 798324545 993562835 648630220 121118794 704799702 234536833 593659058 210111634 129445937 581293534 860570182 100741714 62525672 643301356 867541564 102807677 274871026 907745968 974630638 172113226 24895019 38118067 187623388 418084020 73167315 992211585 540495910 126002938 526161679 733407533 704404244 297633567 702065511 140607179 511384207 138474859 302353735 106637557 898666405 422414824 957503102 347640647 303683848 657132773 127120065 650614755 135326096 928701815 928195625 241147886 373323445 311555059 157512625 64448017 642464021 836748406 594653625 193780473 703800052 958628701 561143430 627402711 738816695 307499981 304917183 68525280 590245224 432646700 676608497 89671118 65412405 984926886 777317645 523072605 253651953 825217449 312784101 474021071 550891922 372410985 459640498 622080105 744689329 711826269 632313489 55486963 53949197 285358272 713004545 699537468 80055304 889156369 14894182 326143124 159909672 317305747 564859274 514359121 583907480 893278926 906998807 258819146 943832996 245710092 736256029 146372447 175477569 278022877 973186450 737668335 542034050 291472787 43282638 221461600 168624932 85695942 749063435 670406298 330233347 826651602 835991275 736796812 481441186 677218900 913724657 485324710 842804392 299539633 804554758 352688222 878281821 789785487 375090166 765625003 729647409 318899034 730121713 566331021 744940854 464565440 30164746 327049347 223538849 874751285 622810299 111211027 521913421 125641072 377065823 352773701 609418295 604372460 225606839 689532456 894196739 470770536 316302950 132899660 898483062 452684136 91625589 369386567 764396282 257223346 809560016 363821873 742410269 106624977 590691014 433716775 20490258 90385301 194743181 686825931 244324910 196236176 388068027 70389186 520021612 671405211 57248206 33103669 227884522 434794831 606964646 596682577 952257386 814044301 28956421 607296455 562353106 501470711 506574614 352941388 32336044 439616116 501123043 833619482 220752039 551136432 924054750 529945709 469909524 76549017 991711577 594995976 323934569 278323427 49756941 940605870 313299393 398820741 336838807 48315816 596118875 617898554 510849526 87013957 984257047 572043777 547538191 178697045 280756220 335785118 993997865 276769198 669118389 160834838 751552626 158337960 543635214 144229431 886582392 509272992 760763260 327619854 316280496 9982072 59891859 195766126 279828466 377935381 675507341 758677616 121231354 774376416 27846858 458096877 793744361 708101446 476620874 165684230 270160067 626899512 520585781 365149597 749504495 370952620 421887571 609035481 253412282 242155546 865307541 92889766 333294036 191755263 322771594 9728563 687350225 543806045 107468266 452617074 603232681 937456953 884439311 325389211 399145016 131791388 900283511 837684649 995444159 979303059 810537028 434525915 245633121 506756784 216153276 769270069 696127655 455805830 745567945 932224508 245616125 986707376 483288697 368949822 240111410 36701130 678482303 392971592 489616636 221192951 424219568 536915245 862412914 425648986 194873223 990158150 648716176 717185181 383230626 330513069 212795830 667399789 325528131 862258368 493767209 316592891 637551569 496679844 462685329 747263868 482663252 96540352 340883321 565629098 612522492 629471550 316522195 529024322 509101722 204797069 187057265 356785796 448245284 52369121 897552525 635735222 174448182 449728433 98366018 584179105 840067980 755855929 944818192 434643218 900654730 530430966 978869852 373158235 937556404 398682412 633007597 170866127 134496822 333582179 793384049 469523273 447852124 832237030 922249462 684326566 387700763 743269443 194754673 98229062 353269639 398685389 324112442 357797263 272131419 220301085 737889934 970930026 285984116 118240397 679005964 203267268 998504790 252052668 167773497 721229839 876271781 710982157 785168636 67110590 610919853 587119655 905584418 90533324 419034076 265204342 125245403 43879990 933030466 869210793 218024763 425394044 677636632 597740850 135637434 191561252 798256950 860826057 124070580 49376311 804030619 899484649 692147946 224145346 586553576 352365906 410387200 297508695 866968805 545859205 776865277 716051593 452730875 201162059 294386126 914040435 362286265 882093871 244446658 250506290 318557008 780196351 238719247 922152294 817118743 253815375 106492236 550485174 968448007 876957685 816895733 193003081 98869055 175385230 282917867 241850957 840996737 796421112 542913009 239741299 436508851 328611030 227853104 216498033 575358816 262114064 795402419 255993215 80813365 73028176 261481196 173720283 855924612 983113861 599169581 585187653 86571972 745527396 276557104 819220867 373555214 963928546 59529104 527524318 992659362 281668795 395835982 32126115 202790240 449825006 856825933 47604388 535404624 35430207 336513749 350767540 231579162 870754228 602568212 840569135 436520847 998611993 108239256 484102767 339184414 41045628 298519766 132364632 716200799 649471921 626336679 748184781 739155852 395885519 340170437 277594936 18589699 954780336 629688915 22196486 447247046 316275317 177545810 484773673 217895418 499684864 706966317 810685332 305348715 400037753 807539758 843015619 755659271 866153674 465432070 510590256 463451231 123712035 412307785 420169695 93701417 818564214 913862383 745700051 649789120 329634811 112696533 747140246 432271522 430494894 401717818 209685429 374313457 308409548 784596546 750352706 478678003 14672730 389805687 130122065 114234514 497095838 24685379 226571131 699998941 373705380 667829878 188761950 778648965 637749178 608450502 502301466 545393505 735768820 428748106 107761109 507906538 701953193 292243967 556995129 944468416 887204596 535428675 486455537 923354915 465757748 898837085 617163055 791657594 244899212 595622131 121606953 653540560 166307171 525557649 436112023 661930066 932057574 833939241 967837495 968968402 766608257 916019342 378230602 713043527 931712362 408483064 710584340 750132043 914778646 170782339 879530591 62722459 190817218 281062575 197165304 104172699 510458091 138328289 102110513 686975440 23763670 165386977 734437726 563542883 150617609 128106331 178277720 957718181 192244944 991780446 179573501 35302533 622984121 622670815
